// 巴什博弈(Bash Game)
// 一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子
// 拿到最后一颗石子的人获胜，根据n、m返回谁赢

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1001;
string dp[MAXN][MAXN];

// 动态规划进行所有尝试
// 为了验证
string bashGame1(int n, int m)
{
    if(n == 0) return "后手";
    if(!dp[n][m].empty()) dp[n][m];
    string ans = "后手";
    for(int pick = 1; pick <= m; ++pick)
    {
        if(bashGame1(n - pick, m) == "后手")
        {
            // 后续过程的后手，就是此时的先手
            ans = "先手";
            break;
        }
    }
    dp[n][m] = ans;
    return ans;
}

// 正式方法
string bashGame2(int n, int m)
{
    return n % (m + 1) != 0 ? "先手" : "后手";
}

int main()
{
    // 为了验证
    srand(time(nullptr));
    int V = 500; // 需要比MAXN小
    int testTimes = 5000;
    cout << "测试开始" << endl;
    for(int i = 0; i < testTimes; ++i)
    {
        int n = rand() % V;
        int m = rand() % V + 1;
        string ans1 = bashGame1(n, m);
        string ans2 = bashGame2(n, m);
        if(ans1 != ans2) cout << "出错了！" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}